package mytest.google;

import java.util.Stack;

public class Test {

	static class Node{
		Node left,right;
		int data;
	}
	
	
	
	static Node solve(Node root)
	{
		int max=0;
		Node result=null;
		Stack<Node> stack =new Stack<Node>();
		Stack<Integer> flag=new Stack<Integer>();
		Node p=root;
		while(!stack.empty()||p!=null)
		{
			if(p!=null)
			{
				stack.push(p);
				flag.push(0);
				p=p.left;
			}else {
				
				if(flag.peek()==1)
				{
					p=stack.pop();
					flag.pop();
					if(p.data>max)
					{
						max=p.data;
						result=p;
					}
					if(!stack.empty())stack.peek().data+=p.data;
				}
				
				flag.pop();
				flag.push(1);
				p=stack.peek().right;
			}
		}
		return result;
	}
	
	
	public static void main(String[] args) {

		Node root=new Node();
		root.data=1;
		Node p=new Node();
		p.data=2;
		root.left=p;
		p=new Node();
		p.data=-1;
		root.right=p;
		
		p=new Node();
		p.data=3;
		
		root.left.left=p;
		
		p=new Node();
		p.data=-5;
		
		root.left.right=p;
		
		p=new Node();
		p.data=-1;
		root.right=p;
		
		p=new Node();
		p.data=2;
		
		root.right.left=p;
		
		
		System.out.println(solve(root).data);
	}

}
